package org.example;

public class Test1 {
    //leetcode 判断子序列 https://leetcode.cn/problems/is-subsequence/description/?envType=study-plan-v2&envId=top-interview-150
    /**
     * 指针解决
     */
    public boolean isSubsequence(String s, String t) {
        int n1 = s.length(), n2 = t.length();
        int index1 = 0, index2 = 0;
        while (index1 < n1 && index2 < n2) {
            if (s.charAt(index1) == t.charAt(index2)) index1++;
            index2++;
        }
        return index1 >= n1;
    }

    public boolean isSubsequence2(String s, String t) {
        //dp求出两个字符串最长子序列的长度，如果长度等于s字符串的长度，那就说明s为t的子序列
        int n1 = s.length(), n2 = t.length();
        int[][] dp = new int[n1+1][n2+1];
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (s.charAt(i-1) == t.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
                dp[i][j] = Math.max(dp[i][j],Math.max(dp[i-1][j],dp[i][j-1]));
            }
        }
        return dp[n1][n2] == n1;
    }
}
